#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<stack>
#include<list>
#include<assert.h>
#include"reverse_iterator.h"

using namespace std;

namespace my_list
{
	template<class T>
	struct List_node
	{
		struct List_node<T>* pre_;
		struct List_node<T>* next_;
		T val_;

		List_node(const T& x = T()):val_(x),pre_(nullptr),next_(nullptr)//构造函数
		{}
	};

	template<class T, class Ref, class Ptr>
	struct list_iterator
	{
		typedef List_node<T> Link_type;//给模板节点类型起别名
		typedef list_iterator<T, Ref, Ptr> self;//给这个比较长的类型起别名，等会要做返回值使用
		typedef list_iterator<T, T&, T*>             iterator;
		typedef Ref Ref;//把这个模板类型变成我们类里面的类型，之后反向迭代器要使用
		typedef Ptr Ptr;//把这个模板类型变成我们类里面的类型，之后反向迭代器要使用

		list_iterator() {};//空的构造函数
		list_iterator(Link_type* x) :node(x)//用节点指针构造的构造函数
		{
		}

		list_iterator(const iterator& x) : node(x.node)//拷贝构造函数
		{
		}
		Ref operator*() const//返回这个值的引用
		{
			return node->val_;
		}

		Ptr operator->() const//返回这个节点指针，让迭代器可以使用箭头访问这个节点的值（主要用于list保存的结构体类型的情况）
		{
			return &node->val_;
		}

		self operator++(int)//后置++
		{
			self tmp(node);
			node = node->next_;
			return tmp;
		}

		self& operator++()//前置++
		{
			node = node->next_;
			return *this;
		}

		self& operator--()//前置--
		{
			node = node->pre_;
			return *this;
		}

		self operator--(int)//后置--
		{
			self tmp(node);//先构造现在的迭代器
			node = node->pre_;//再更新当前迭代器的node
			return tmp;//返回的是没--前的迭代器
		}

		bool operator!=(const self& x) const //判断迭代器是否相等，看他们保存的节点指针是否一样即可
		{
			return node != x.node;
		}

		bool operator==(const self& x) const
		{
			return node == x.node;
		}
		Link_type* node;
	};

	

	template<class T>
	class list
	{
	public:
		typedef struct List_node<T> list_type;//给类模板起别名，因为后面我们用的比较多，这个类模板的类型名字太长了
		typedef struct list_iterator<T,T&,T*> iterator;//普通给迭代器类型起别名
		typedef struct list_iterator<T,const T&,const T*> const_iterator;//给const迭代器类型起别名
		typedef struct my_reverse_iterator::reverse_iterator<iterator> reverse_iterator;//给反向迭代器类型起别名

		void Init_empty()//初始化list的容器，因为list的底层是带头的，所以就算是空构造也要给这个对象创建一个头节点
		{
			Head_ = new list_type;//开空间

			//初始化
			Head_->val_ = T();
			Head_->pre_ = Head_;
			Head_->next_ = Head_;
		}
		list()//空的构造
		{
			Init_empty();
		}

		list(const list& x)//拷贝构造
		{
			Init_empty();
			for (auto i: x)//复用尾插和迭代器
			{
				push_back(i);
			}
		}

		list(size_t n, const T& val = T())//普通构造
		{
			Init_empty();//初始化头节点
			for (int i = 0; i < n; ++i)//尾插数据
				push_back(val);
		}

		list(int n, const T& val = T())//普通构造
		{
			Init_empty();
			for (int i = 0; i < n; ++i)
				push_back(val);
		}

		template <class InputIterator>
		list(InputIterator first, InputIterator last)//迭代器区间构造
		{
			Init_empty();//初始化头节点
			while (first != last)//迭代器遍历并初始化
			{
				push_back(*first);
				first++;
			}
		}

		list<T>& operator=(const list<T>& x)//赋值运算符重载
		{
			list<T> tmp(x);//复用拷贝构造
			std::swap(tmp.Head_,Head_);//交换它们的Head_节点

			return *this;
		}

		iterator begin()//普通迭代器的开始访问函数，从头节点的下一个节点开始访问
		{
			return Head_->next_;
		}

		iterator end()//普通迭代器的结束访问函数，访问到头节点就不能访问了，因为是双向循环链表
		{
			return Head_;
		}

		const_iterator begin() const
		{
			return Head_->next_;
		}

		const_iterator end() const
		{
			return Head_;
		}

		reverse_iterator rbegin()//反向迭代器的开始访问函数，从普通迭代器的end()前面的那个节点开始访问。
		{
			return --end();
		}

		reverse_iterator rend()//和end()一样
		{
			return end();
		}

		void push_back(const T& val)//尾插
		{
			list_type* newnode = new list_type(val);//创建新的节点

			list_type* tail = Head_->pre_;//保存尾节点
			
			newnode->pre_ = tail;//先把新节点的前驱节点指向尾节点
			newnode->next_ = Head_;//再把新节点的后继节点指向头节点

			Head_->pre_ = newnode;//更新头节点的前驱节点
			tail->next_ = newnode;//更新尾节点的后继节点
		}

		void pop_back()//尾删
		{
			assert(Head_->next_ != Head_);//检查list中是否还有数据

			list_type* tail = Head_->pre_;//先保存尾节点

			tail->pre_->next_ = Head_;//把尾节点的前驱节点的后继节点指向head_
			Head_->pre_ = tail->pre_;//再把头节点的前驱节点指向尾节点的前驱节点

			delete tail;//释放当前尾节点的空间
		}

		void push_front(const T& val)//头插
		{
			list_type* newnode = new list_type(val);//创建新的节点

			newnode->next_ = Head_->next_;//新节点的next先指向头节点的next
			newnode->pre_ = Head_;//新节点的前驱节点指向Head_
			Head_->next_ = newnode;//头节点的后继节点指向新节点
		}

		void pop_front()//头删
		{
			assert(Head_->next_ != Head_);//如果只剩下头节点，就不能继续删除了

			list_type* node = Head_->next_;//先保存要删除的节点，防止重新链接之后找不到，造成内存泄漏

			Head_->next_ = node->next_;//先把头节点的后继节点指向待删除节点的后继节点
			node->next_ ->pre_ = Head_;//再把待删除节点的后继节点的前驱节点指向头节点
			delete node;//释放node节点
		}

	    iterator insert(iterator position, const T& val)//在position迭代器指向的地址之前，插入元素val
		{
			list_type* newnode = new list_type(val);//创建新的节点
			list_type* pre = position.node->pre_;

			//链接起来
			pre->next_ = newnode;
			newnode->pre_ = pre;
			newnode->next_ = position.node;
		    position.node->pre_ = newnode;

			return --position;//返回第一个新插入元素的迭代器
		}

		iterator erase(iterator position)
		{
			assert(position.node != Head_);//检查是否还有节点

			list_type* pre = position.node->pre_;//保存前驱节点

			//链接
			pre->next_ = position.node->next_;
			position.node->next_->pre_ = pre;

			//删除
			delete position.node;

			//返回被删除的最后一个位置的下一个元素的迭代器
			return iterator(pre->next_);
		}

		size_t size() const
		{
			list_type* cur = Head_->next_;//保存头节点的后继节点
			size_t size = 0;//保存节点的个数
			while (cur != Head_)
			{
				cur = cur->next_;//继续遍历
				size++;
			}
			return size;
		}
		
		void clear() 
		{
			list_type* cur = Head_->next_;//保存头节点的后继节点
			while (cur != Head_)//如果cur不等于Head_节点就继续
			{
				list_type* next = cur->next_;//先保存后继节点
				delete cur;//释放当前节点
				cur = next;
			}

			//不要忘记更新头节点的链接，不然就会指向野指针了
			Head_->next_ = Head_;
			Head_->pre_ = Head_;
		}

		void swap(list<T>& x)
		{
			std::swap(Head_, x.Head_);
		}
		~list()
		{
			clear();//调用析构函数
			delete Head_;//释放头节点
			Head_ = nullptr;
		}
	private:
		
		list_type* Head_;
	};

	template<class T>
	void swap(list<T>& x, list<T>& y)
	{
		x.swap(y);
	}
	template<class T>
	void print_list(T& list1)
	{
		cout << "list: ";
		for (auto& i : list1)
		{
			cout << i << " ";
		}
		cout << endl;
	}
}
	